/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/bomb-enemy
   @Language: C++
   @Datetime: 19-06-04 10:52
   */

// Method 1, Time O(m*n), Space O(m*n), Time 353ms
class Solution {
public:
	/**
	 * @param grid: Given a 2D grid, each cell is either 'W', 'E' or '0'
	 * @return: an integer, the maximum enemies you can kill using one bomb
	 */
	int maxKilledEnemies(vector<vector<char> > &grid) {
		// write your code here
		if(grid.size()==0 || grid[0].size()==0) return 0;
		int m=grid.size(), n=grid[0].size(), mx=0;
		vector<vector<int> > dp(m, vector<int>(n,0));
		for(int i=0; i<m; ++i){
			vector<int> rows(n,0);
			for(int l=0, j=0; j<n; ++j){
				if(grid[i][j]=='E') ++l;
				else if(grid[i][j]=='W') l=0;
				else rows[j]+=l;
			}
			for(int r=0, j=n; j--;){
				if(grid[i][j]=='E') ++r;
				else if(grid[i][j]=='W') r=0;
				else rows[j]+=r;
			}
			for(int j=n; j--; dp[i][j]+=rows[j]);
		}
		for(int j=0; j<n; ++j){
			vector<int> cols(m,0);
			for(int u=0, i=0; i<m; ++i){
				if(grid[i][j]=='E') ++u;
				else if(grid[i][j]=='W') u=0;
				else cols[i]+=u;
			}
			for(int d=0, i=m; i--;){
				if(grid[i][j]=='E') ++d;
				else if(grid[i][j]=='W') d=0;
				else cols[i]+=d;
			}
			for(int i=m; i--; mx=max(mx,dp[i][j]))
				dp[i][j]+=cols[i];
		}
		return mx;
	}
};


// Method 2, Time O(m*n*k), Space O(n), Time 352ms
class Solution {
public:
	/**
	 * @param grid: Given a 2D grid, each cell is either 'W', 'E' or '0'
	 * @return: an integer, the maximum enemies you can kill using one bomb
	 */
	int maxKilledEnemies(vector<vector<char> > &grid) {
		// write your code here
		if(grid.size()==0 || grid[0].size()==0) return 0;
		int m=grid.size(), n=grid[0].size(), mx=0;
		vector<int> cols(n,0);
		for(int i=0; i<m; ++i){
			for(int j=0, row=0; j<n; ++j){
				if(j==0 || grid[i][j-1]=='W'){
					row=0;
					for(int k=j; k<n; ++k){
						if(grid[i][k]=='E') ++row;
						if(grid[i][k]=='W') break;
					}
				}
				if(i==0 || grid[i-1][j]=='W'){
					cols[j]=0;
					for(int k=i; k<m; ++k){
						if(grid[k][j]=='E') ++cols[j];
						if(grid[k][j]=='W') break;
					}
				}
				if(grid[i][j]=='0') mx=max(mx,row+cols[j]);
			}
		}
		return mx;
	}
};
